package leetCode.sample;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class MergeKListsSolution {


    @Test
    public void test() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;


        ListNode r1 = new ListNode(1);
        ListNode r2 = new ListNode(3);
        ListNode r3 = new ListNode(4);
        r1.next = r2;
        r2.next = r3;

        ListNode z1 = new ListNode(2);
        ListNode z2 = new ListNode(6);
        z1.next = z2;

        ListNode[] lists = new ListNode[]{l1, r1, z1};

        ListNode listNode = mergeKLists2(lists);
        System.out.println(listNode.val);
        while (listNode.next != null) {
            listNode = listNode.next;
            System.out.println(listNode.val);
        }
        listNode = mergeKLists2(new ListNode[1]);
        assert listNode == null;
    }


    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        List<ListNode> list = new ArrayList<>(Arrays.asList(lists));
        list.removeIf(Objects::isNull);
        ListNode head = new ListNode(-1);
        ListNode tmp = head;
        boolean hasNext = true;
        while (hasNext) {
            ListNode min = null;
            int index = 0;
            for (int i = 0; i < list.size(); i++) {
                if (min == null || (list.get(i) != null && list.get(i).val < min.val)) {
                    min = list.get(i);
                    index = i;
                }
            }
            if (min != null) {
                tmp.next = min;
                tmp = tmp.next;
                list.remove(index);
                if (min.next != null) {
                    list.add(min.next);
                    tmp.next = null;
                }
            }
            if (list.size() == 0) {
                hasNext = false;
            }
        }
        return head.next;
    }

    /**
     * @desc: 分治思路，两两比较，然后合并
     * @method: mergeKLists2
     * @param: [lists]
     * @return: leetCode.sample.ListNode
     * @auther: zhipingzhang
     * @date: 2019/12/5 17:35
     */
    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);

    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int middle = (right + left) / 2;
        ListNode leftNode = merge(lists, left, middle);
        ListNode rightNode = merge(lists, middle + 1, right);

        return merge(leftNode, rightNode);
    }

    private ListNode merge(ListNode leftNode, ListNode rightNode) {
        if (leftNode == null) {
            return rightNode;
        }
        if (rightNode == null) {
            return leftNode;
        }
        if (leftNode.val < rightNode.val) {
            leftNode.next = merge(leftNode.next, rightNode);
            return leftNode;
        } else {
            rightNode.next = merge(leftNode, rightNode.next);
            return rightNode;
        }
    }
}
